// 像数组、栈、队列、默认都是线性结构类型。常见的树形结构有二叉树和多叉树（大于两个叉的树）。

// 开发中常见的树形结构有: 文件夹目录、DOM结构、路由的配置...... （树的数据结构是非常重要的）
// 常见概念
// 节点 （根节点、父节点、字节点、兄弟节点）
// 子树 （左子树、右子树）,子树的个数称之为度
// 叶子节点 （度为0的节点） 非叶子节点 （度不为0的节点）
// 节点的深度 （从根节点到当前节点所经过的节点总数）
// 节点的高度 （从当前节点到最远叶子节点经过的节点总数）
// 树的层数 （树的高度、树的深度）
// 有序树( 节点按照顺序排列）、无序树

// 二叉树
// 二叉树是每个结点最多有两个子树的树结构 ，每个节点的度最多为2。 通常子树被称作“左子树”（left subtree）和“右子树”（right subtree） ，左子树和右子树是有顺序的

// 什么是二叉搜索树？
// 一般情况下存储数据我们可以采用数组的方式，但是从数组中检索数据的时间复杂度是O(n),如果数据存储有序，则可以采用二分查找的方式来检索数据，复杂度为:O(logn),但是如果操作数组中的数据像增加、删除默认数组会产生塌陷。时间复杂度为O(n)
// 二叉搜索树中查询、增加、删除复杂度最坏为O(logn)，特性是当它的左子树不空，则左子树上所有结点的值均小于它的根结点的值，当右子树不空，则右子树上所有结点的值均大于它的根结点的值。

// 二叉搜索树的主要操作
// add 添加元素
// remove 删除元素
// size 元素个数
// contains 包含元素

// 二叉搜索树中的数据必须具有可比较性




class Node {
    constructor(element, parent) {
        this.element = element;
        this.parent = parent;
        this.left = null;
        this.right = null;
    }
}
class BST {
    constructor() {
        this.size = 0;
        this.root = null;
    }
    // insertNode(root, element) { // 不停的改变root 作为根节点
    //     let current = root;
    //     if (element < current.element) {
    //         if (current.left) {
    //             this.insertNode(current.left, element); // current.left
    //         } else {
    //             current.left = new Node(element, current)
    //         }
    //     } else {
    //         if (current.right) {
    //             this.insertNode(current.right, element); // current.right
    //         } else {
    //             current.right = new Node(element, current)
    //         }
    //     }
    // }
    compare(e1,e2){
        return e1 - e2
    }
    add(element) {
        if (this.root === null) {
            this.root = new Node(element, null);
        } else {
            // this.insertNode(this.root, element)
            let current = this.root;
            let parent;
            let v;
            while(current !== null){
                // v 决定是放左边还是放右边
                v =  this.compare(element,current.element); // 用当前的插入元素 和 根元素比较
                parent = current; // parent决定了把数据放在谁的下面
                if(v < 0){
                    current = current.left; // 如果比当前节点小的 放在左边
                }else if(v > 0){
                    current = current.right
                }else{
                    current.element = element; // 直接用新的覆盖掉老的
                }
            }
            // current = null
            let node  = new Node(element,parent)
            if(v < 0){
                parent.left = node
            }else {
                parent.right = node
            }
        }
        this.size++;
    }
}

let bst = new BST();

[10, 8, 6, 12, 32, 2, 100,7].forEach(item => {
    bst.add(item);
})


console.dir(bst,{depth:1000})
